[C] Indexed Priority Queue (Indexed Heap)

a[] 라는 배열이 주어지고, heap[]으로 변환. heap[]상에 있는 a[i]에 해당하는 값을 바로 수정하고, heap 을 유지할 수 있는 자료구조. 만약 단순 heap으로 이를 구현한다면, update가 일어날때마다 n만큼 배열을 탐색해 a[i]를 수정한 뒤, 배열을 통째로 heapify를 하면 O(N) + O(N) 이 된다. 하지만 indexed heap을 통해 특정 배열값만 수정 ...

heapindexed priority queueheap